package com.programmercarl.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode.cn/problems/subsets-ii/description/
 * 子集Ⅱ
 *
 * @author yulongtian
 * @create 2025-01-11 13:39
 */
public class Test09 {
    public static void main(String[] args) {
        Test09 test09 = new Test09();
        System.out.println(test09.subsetsWithDup1(new int[]{1, 2, 2}));
    }

    /**
     * 循环迭代 无重复的子集
     * https://leetcode.cn/problems/subsets/description/
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        for (int i = 0; i < nums.length; i++) {
            List<List<Integer>> temp = res;
            int size = temp.size();
            for (int j = 0; j < size; j++) {
                List<Integer> copy = new ArrayList<>(temp.get(j));
                copy.add(nums[i]);
                temp.add(copy);
            }
            res = temp;
        }
        return res;
    }

    /**
     * 回溯方法 可以
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> subsetsWithDup1(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> path = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        backtrack(nums, 0, ans, path, used);

        return ans;
    }

    public void backtrack(int[] nums, int index, List<List<Integer>> ans, List<Integer> path, boolean[] used) {
        ans.add(new ArrayList<>(path));
        if (index == nums.length) {
            return;
        }
        for (int i = index; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            backtrack(nums, i + 1, ans, path, used);
            used[i] = false;
            path.remove(path.size() - 1);
        }
    }

}
